﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0033_SortedSquares : IAlgorithm
    {
        // 977. 有序数组的平方

        // 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

        // 提示：
        //  1 <= nums.length <= 10^4
        //  -10^4 <= nums[i] <= 10^4
        //  nums 已按 非递减顺序 排序

        // 进阶：
        //  请你设计时间复杂度为 O(n) 的算法解决本问题


        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 1, 3, 10 };
            //var nums = new int[] { -4, -2, -1, 1, 3, 10 };
            // 算法执行与打印
            foreach (var item in SortedSquares(nums))
            {
                Console.WriteLine(item);
            }
        }

        // 算法
        // 双指针，倒序添加最大值
        public int[] SortedSquares(int[] nums)
        {
            var result = new int[nums.Length];
            int s = 0, e = nums.Length - 1;
            for (int i = result.Length - 1; i >= 0; i--)
                if (nums[s] * nums[s] > nums[e] * nums[e])
                    result[i] = nums[s] * nums[s++];
                else
                    result[i] = nums[e] * nums[e--];
            return result;
        }
    }
}
